import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public class Shell {

    private Shell() {}

    public static void sort(Comparable<?>[] a) {
        int n = a.length;
        // 3x+1 increment sequence: 1,4,13,40,121,364,1093,...
        int h = 1;
        while(h < n/3) 
            h = 3 * h + 1;
        // the first value of h is maximum in this list.
        while(h >= 1) {
            for(int i = h; i < n; i++) {
                for(int j = i; j >= h && less(a[j], a[j-h]); j -= h) {
                    exch(a, j, j-h);
                }
            }
            assert isHsorted(a, h);
            h /= 3;
        }

        assert isSorted(a);

    }

    private static boolean less(Comparable v, Comparable w) {

        return v.compareTo(w) < 0;
        
    }


    private static void exch(Object[] a, int i, int j) {
        Object swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }

    private static boolean isSorted(Comparable<?>[] a) {
        for(int i = 1; i < a.length; i++) {
            if(less(a[i], a[i-1]))
                return false;
        }
        return true;
    }
    // is the array h-sorted ?
    private static boolean isHsorted(Comparable<?>[] a, int h) {
        for(int i = h; i < a.length; i++) {
            if(less(a[i], a[i-h]))
                return false;
        }
        return true;

    }

    private static void show(Comparable<?>[] a) {
        for(int i = 0; i < a.length; i++) {
            StdOut.println(a[i]);
        }
    }

    public static void main(String[] args) {
        /*
        int[] b = StdIn.readAllInts();
        StdOut.printf("b.length=%d\r\n", b.length);
        Integer[] a = new Integer[b.length];
        for(int i = 0; i < b.length; i++)
        {
            a[i] = b[i];
        }
        Shell.sort(a);
        show(a);
        */
        String[] a = StdIn.readAllStrings();
        Shell.sort(a);
        show(a);
    }

}
